package binarytree

func zigzagLevelOrder(root *TreeNode) [][]int {

	ans := [][]int{}

	if root == nil {
		return ans
	}

	queue := []*TreeNode{root}
	curLen := 1
	curLevel := 0
	nextLen := 0

	for len(queue) != 0 {

		levelAns := []int{}
		for curLen > 0 {
			node := queue[0]
			if node.Left != nil {
				queue = append(queue, node.Left)
				nextLen++
			}
			if node.Right != nil {
				queue = append(queue, node.Right)
				nextLen++
			}
			levelAns = append(levelAns, node.Val)
			queue = queue[1:]
			curLen--
		}

		curLen = nextLen
		nextLen = 0
		if curLevel%2 == 1 {
			for i := 0; i < len(levelAns)/2; i++ {
				levelAns[i], levelAns[len(levelAns)-i-1] = levelAns[len(levelAns)-i-1], levelAns[i]
			}

		}
		ans = append(ans, levelAns)
		curLevel++

	}

	return ans

}
